/***************************************
 Author       : LIN
 Email        : l2441473911@163.com
 LastModified : 2020-12-25 12:35
 FileName     : bit-stack.c
 Description  : A stack that stores bits
**************************************/
#include "./bit-stack.h"


// capacity is required to be a muiltiple of 8
BitStack *CreateBitStack(int capacity){
	if(capacity <= 0 || capacity % BITS_PRE_BYTE != 0)
		return NULL;

	int bytes_number = capacity / BITS_PRE_BYTE;

	BitStack *newStack = (BitStack *)malloc(sizeof(BitStack));
	unsigned char *stack_body = (unsigned char *)malloc(bytes_number);

	// initialize all bits to zero
	for(bytes_number--; bytes_number >= 0; bytes_number--)
		stack_body[bytes_number] = 0x00u;

	newStack->capacity = capacity;
	newStack->top = -1;
	newStack->stack_body = stack_body;

	return newStack;
}

void DisposeBitStack(BitStack *s){
	if(s != NULL){
		free(s->stack_body);
		free(s);
	}
}

int BitStackPush(BitStack *s, unsigned char bit){
	if(s == NULL || s->top + 1 >= s->capacity)
		return 0;

	(s->top)++;
	// we merely increase size if bit is 0.
	// this is valid only when we have ini-
	// tialized the array to all-zero and 
	// the pop operation clears the top bit 
	// rather than leaving it be.
	if(bit == 0x01u){
		unsigned int byte_index = s->top / BITS_PRE_BYTE;
		unsigned int bit_index = s->top - BITS_PRE_BYTE * byte_index;

		s->stack_body[byte_index] |= (0x80u >> bit_index);
	}

	return 1;
}

int BitStackPop(BitStack *s, unsigned char *dataPopped){
	if(s == NULL || s->top < 0)
		return 0;
	
	unsigned int byte_index = s->top / BITS_PRE_BYTE;
	unsigned int bit_index = s->top - BITS_PRE_BYTE * byte_index;
	
	if(dataPopped != NULL)
		*dataPopped = (s->stack_body[byte_index] >> (BITS_PRE_BYTE - bit_index - 1)) & 0x01u;
	
	s->stack_body[byte_index] &= ~(0x80u >> bit_index);

	s->top--;

	return 1;
}

void BitStackShow_TopDown(BitStack *s){
	if(s == NULL || s->top == -1) return;
	int i;
	for(i = s->top; i >= 0; i--)
		printf("%c", '0' + ((s->stack_body[i / BITS_PRE_BYTE] >> (BITS_PRE_BYTE - i % BITS_PRE_BYTE - 1)) & 0x01u));
	putchar('\n');
}

int BitStackCopyStackBottomToTopTo(BitStack *s, unsigned char *dst){
	if(s == NULL || s->top == -1) return 0;

	int i, leastBytesNumber = s->top / BITS_PRE_BYTE + 1;
	
	for(i = 0; i < leastBytesNumber; i++)
		dst[i] = s->stack_body[i];

	return 1;
}

void _ShowBits(unsigned char *d, int n){
	int i;
	for(i = 0; i < n; i++){
		if(d[i / BITS_PRE_BYTE] & (0x80u >> (i % BITS_PRE_BYTE)))
			printf("1");
		else printf("0");
	}
	putchar('\n');
}

//int main(void){
//	BitStack *S = CreateBitStack(16);
//	unsigned char d, c[2];
//
//	BitStackPush(S, 0x01u);
//	BitStackPush(S, 0x00u);
//	BitStackPush(S, 0x01u);
//	BitStackPush(S, 0x01u);
//	BitStackPush(S, 0x00u);
//	BitStackPush(S, 0x01u);
//	BitStackPush(S, 0x00u);
//	BitStackPop(S, NULL);
//	BitStackPush(S, 0x00u);
//	BitStackPush(S, 0x01u);
//	BitStackPop(S, &d);
//	printf("[%d]\n", d);
//
//	BitStackShow_TopDown(S);
//	BitStackCopyStackBottomToTopTo(S, c);
//	_ShowBits(c, S->top + 1);
//	
//	BitStackPop(S, &d);
//	printf("[%d]\n", d);
//	BitStackPop(S, &d);
//	printf("[%d]\n", d);
//	BitStackPop(S, &d);
//	printf("[%d]\n", d);
//
//	BitStackShow_TopDown(S);
//	BitStackCopyStackBottomToTopTo(S, c);
//	_ShowBits(c, S->top + 1);
//
//	DisposeBitStack(S);
//
//	return 0;
//}
//
